Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 10034 - Freckles / p10034.cpp
blob07540a21e1dd78d84af2048bb4de3e2fa21f09d1
1 #include <iostream>
2 #include <cmath>
3 #include <map>
4 #include <queue>
5 #include <set>
7 using namespace std;
9 typedef pair<double, double> point;
10 //Gives a vector of adjacent nodes to a point
11 typedef map< point, vector<point> > graph;
12 //Edge of length "first" that arrives to point "second"
13 typedef pair<double, point> edge;
15 double euclidean(const point &a, const point &b){ return hypot(a.first-b.first, a.second-b.second);}
18 int main(){
19 int casos;
20 cin >> casos;
21 while (casos--){
22 graph g;
23 int n;
24 cin >> n;
25 while (n--){
26 double x,y;
27 cin >> x >> y;
28 point p(x,y);
29 if (g.count(p) == 0){ //Si no está todavía
30 vector<point> v;
31 g[p] = v;
32 for (graph::iterator i = g.begin(); i != g.end(); ++i){
33 if ((*i).first != p){
34 (*i).second.push_back(p);
35 g[p].push_back((*i).first);
41 set<point> visited;
42 priority_queue<edge, vector<edge>, greater<edge> > q;
43 //Each edge in q has got a length "first" and a point "second".
44 //It means I can reach point "second" which is "first" meters away.
45 //q has the closest reachable node on top (I may have already visited it!)
46 q.push(edge(0.0, (*g.begin()).first));
47 double totalDistance = 0.0;
48 while (!q.empty()){
49 edge nearest = q.top();
50 q.pop();
51 point actualNode = nearest.second;
52 if (visited.count(actualNode) == 1) continue; //Ya habia visitado este
53 totalDistance += nearest.first;
54 visited.insert(actualNode);
55 vector<point> neighbors = g[actualNode];
56 for (int i=0; i<neighbors.size(); ++i){
57 point t = neighbors[i];
58 double dist = euclidean(actualNode, t);
59 q.push(edge(dist, t));
62 printf("%.2f\n", totalDistance);
63 if (casos > 0) cout << endl; //Endl between cases